#include <bits/stdc++.h>

using namespace std;

// 最大数
// 给定一组非负整数nums
// 重新排列每个数的顺序（每个数不可拆分）使之组成一个最大的整数
// 测试链接 : https://leetcode.cn/problems/largest-number/

class Solution 
{
public:
    string largestNumber1(vector<int>& nums) 
    {
        sort(nums.begin(), nums.end(), [](int a, int b){
            string num1 = to_string(a);
            string num2 = to_string(b);
            return num1 + num2 > num2 + num1;
        });
        if(nums[0] == 0) return "0";
        string ans;
        for(int x : nums) ans += to_string(x);
        return ans;
    }

    string largestNumber2(vector<int>& nums) 
    {
        int n = nums.size();
        string strs[n];
        for(int i = 0; i < n; ++i) strs[i] = to_string(nums[i]);
        sort(strs, strs + n, [](string& a, string& b){
            return a + b > b + a;
        });
        if(strs[0] == "0") return "0";
        string ans;
        for(string& s : strs) ans += s;
        return ans;
    }
};

// 全排列代码，讲解038，常见经典递归过程解析
void f(vector<string>& strs, int i, vector<string>& ans)
{
    if(i == strs.size())
    {
        string path;
        for(string& s : strs) path += s;
        ans.emplace_back(path);
    }
    else
    {
        for(int j = i; j < strs.size(); ++j)
        {
            swap(strs[i], strs[j]);
            f(strs, i + 1, ans);
            swap(strs[i], strs[j]);
        }
    }
}

// strs中全是非空字符串，要把所有字符串拼接起来，形成字典序最小的结果
// 暴力方法
// 为了验证
// 生成所有可能的排列
// 其中选出字典序最小的结果
string way1(vector<string>& strs)
{
    vector<string> ans;
    f(strs, 0, ans);
    sort(ans.begin(), ans.end());
    return ans[0];
}

// strs中全是非空字符串，要把所有字符串拼接起来，形成字典序最小的结果
// 正式方法
// 时间复杂度O(n*logn)
string way2(vector<string>& strs)
{
    sort(strs.begin(), strs.end(), [](string& a, string& b){
        return a + b < b + a;
    });
    string ans;
    for(string& s : strs) ans += s;
    return ans;
}

// 为了验证
// 生成长度1~m，字符种类有v种，随机字符串
string randomString(int m, int v)
{
    int len = rand() % m + 1;
    string ans;
    for(int i = 0; i < len; ++i)
    {
        ans += ('a' + (rand() % v + 1));
    }
    return ans;
}

// 为了验证
// 生成长度1~n的随机字符串数组
vector<string> randomStringArray(int n, int m, int v)
{
    vector<string> ans(rand() % n + 1);
    for(int i = 0; i < ans.size(); ++i)
    {
        ans[i] = randomString(m, v);
    }
    return ans;
}

int main()
{
    // 为了验证
	// 对数器
    srand(time(nullptr));
    int n = 8; // 数组中最多几个字符串
    int m = 5; // 字符串长度最大多长
    int v = 4; // 字符的种类有几种
    int testTimes = 2000;
    cout << "测试开始" << endl;
    for(int i = 1; i <= testTimes; i++)
    {
        vector<string> strs = randomStringArray(n, m, v);
        string ans1 = way1(strs);
        string ans2 = way2(strs);
        if(ans1 != ans2)
        {
            // 如果出错了
            // 可以增加打印行为找到一组出错的例子
            // 然后去debug
            cout << "出错了！" << endl;
        }
        if(i % 100 == 0)
        {
            cout << "(测试到第" << i << "组)" << endl;
        }
    }
    cout << "测试结束" << endl;

    return 0;
}